(1) Field of the Invention
The present invention relates to a multipoint data packet switched communication system and a communication apparatus for controlling access and resolving conflicts on a shared communication medium.
(2) Prior Art
Packet switching networks came into existence in response to the need for efficient and economical data communications. As networks grew, there has been a need for inexpensive, high-capacity communication channels. Satellite communication technology may offer a solution with its broadband channels. The satellite acts as a pure transponder repeating whatever it receives and beaming this transmission back down to earth. The satellite is characterized as a high-capacity channel which has a fixed propagation delay that is relatively large compared to the packet transmission time. The difficulty is in controlling access to the channel where the user devices are geographically distributed.
An alternative method of providing communications among a large number of data communication devices is through a ground radio packet switching system. Ground radio systems have been available for many years. The basic principles involved are similar to the satellite packet switching system. In both systems there is a broadcast channel in which, when two or more packet transmissions overlap in part or completely, the packet transmissions will interfere and destroy each other. This is called interference or collision. The fundamental difference is that in the ground radio system, the propagation delay of the medium is small compared to a packet transmission time.
Consider the case of a collection of transceivers, each of which is attempting to transmit over a shared communication channel. When two separate source transmissions overlap in part or completely they will interfere and destroy each other. When the communication channel is characterized with a propagation delay between any source and destination nodes as being relatively small with respect to that of the transmission duration, then it is more efficient to sense if the channel is idle before attempting transmission. The transceiver should be able to listen to the channel through the use of a carrier detect signal. If the carrier signal is heard then the transmitter will realize that the channel is in use and will defer or postpone its transmission until the channel is sensed to be idle.
This property of carrier deference, does not guarantee channel acquisition. Two or more transceivers may detect the channel idle and attempt transmission. However, the detection of carrier from another transmitter may take the end-to-end propagation delay of the medium. Therefore, interference from multiple simultaneous transmissions may occur. The transceiver transmitting determines that its previous transmission was unsuccessful due to the absence of a positive acknowledgement from the receiving node. It then reschedules its transmission of data. The receiving station itself can determine that the transmission was in error through the use of a cyclical redundancy coding of the block.
Consider the case where the transceiver can listen to its own transmission and determine when interference exists. When interference is detected it could then truncate transmission and reduce the collision period. If the smallest transmitted element (bit) on which interference can be detected is less than the propagation time "Td" over the medium, then the channel is guaranteed to be captured after this time "Td". However, the transceiver can only be assured of medium capture after twice the propagation delay which is the round trip time to sense collision. Once a transmission has been in progress for the end-to-end propagation medium time, all transmitters will be deferred and the transmission will complete without collision.
In view of the foregoing, the problem is how to share and control access to the broadcast communication channel with an acceptable level of performance. Several techniques have been employed or proposed in the past. Among these various schemes are the following:
1. Time Division Multiplexing--Round Robin Schemes PA1 2. Time Division Multiplexing--Alternating Priorities PA1 3. Slotted Access PA1 4. Random Access PA1 5. Carrier Sense Multiple Access PA1 6. Aloha Access PA1 7. Reservation Techniques
The small propagation delay ratio for a ground radio system suggests using the packet switched mode of operation known as "Carrier Sense Multiple Access" (CSMA). In a CSMA system, a transceiver or a modem is able to listen to the medium or channel. If a carrier signal is heard, the transceiver realizes that the channel is busy with a transmission from some other transceiver and will postpone its transmission until the channel is sensed to be idle. This method is useless with a satellite system since the sensed channel state provides information about the channel that is ancient history. The rules for deciding when a transceiver may transmit determines the channel capacity. Three types of "persistent CSMA" protocols, known as l-persistent, nonpersistent and p-persistent CSMA, have been proposed and studied. (See for example, Queuing Systems, Vol. II: Computer Applications, L. Kleinrock, John Wiley and Sons, 1976). The various protocols differ by the action a transceiver takes after sensing the channel. When a transceiver determines that its transmission was unsuccessful due to the lack of a positive acknowledgement or an interference detection signal, it reschedules the transmission. In all cases, the retransmission of the packet is according to a randomly distributed transmission delay. Slotted versions of these CSMA techniques can be considered in which the time axis is slotted with the slot size equal to the one-way propagation delay of the medium. Transmission can only be attempted at the beginning of a slot. Nevertheless, retransmission is by a random distribution function.
The problem is to eliminate this random retry which may result in another packet collision during retransmission. An apparatus is required which can control the access to the channel. These are some of the problems this invention overcomes.